package org.example.algo;

/**
 * 归并排序
 * 归并排序和选择排序一样, 归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）
 * @author shenguangyang
 */
public class MergeSort {

    public static void main(String[] args) {
        // int[] arr = new int[] {3, 2, 1};
        int[] arr = genData(100 * 10000, 100000);

        long t1 = System.currentTimeMillis();
        process(arr, 0, arr.length - 1);
//        Arrays.sort(arr);
        long t2 = System.currentTimeMillis();
        System.out.println("sort time: " + (t2 - t1) + " ms");
//        System.out.println(Arrays.toString(arr));
    }

    public static int[] genData(int size, int maxValue) {
        int[] arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i] = (int) (maxValue * Math.random());
        }
        return arr;
    }


    public static void process(int[] in, int lIndex, int rIndex) {
        if (lIndex == rIndex) {
            return;
        }
        int mid = ((rIndex - lIndex) >> 1) + lIndex;
        process(in, lIndex, mid);
        process(in, mid + 1, rIndex);
        mergeSort(in, lIndex, mid, rIndex);
    }

    /**
     * 合并
     */
    public static void mergeSort(int[] in, int lIndex, int mid, int rIndex) {
        // Console.log("lIndex: {}, min: {}, rIndex: {}", lIndex, mid, rIndex);
        int[] tempArr = new int[rIndex - lIndex + 1];
        int i = 0;
        int lPos = lIndex;
        int rPos = mid + 1;
        while (lPos <= mid && rPos <= rIndex) {
            tempArr[i++] = in[lPos] <= in[rPos] ? in[lPos++] : in[rPos++];
        }
        while (lPos <= mid) {
            tempArr[i++] = in[lPos++];
        }

        while (rPos <= rIndex) {
            tempArr[i++] = in[rPos++];
        }

        for (i = 0; i < tempArr.length; i++) {
            in[lIndex + i] = tempArr[i];
        }
        // System.out.println(Arrays.toString(tempArr));
    }
}
